package dataStructure.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author lhn
 * @date 2024-09-09 15:47
 */

public class GraphDemo {
    public static void main(String[] args) {
//        int n = 5;
//        String vertexs[] = {"A", "B", "C", "D", "E"};
//        Graph graph = new Graph(n);
//        for (String vertex : vertexs) {
//            graph.insertVertex(vertex);
//        }
//        graph.insertEdge(0, 1, 1);  // A-B
//        graph.insertEdge(0, 2, 1);  // A-C
//        graph.insertEdge(1, 2, 1);  // B-C
//        graph.insertEdge(1, 3, 1);  // B-D
//        graph.insertEdge(1, 4, 1);  // B-E
//
//        graph.showGraph();
//
//        System.out.print("深度优先：");
//        graph.dfs();    //深度优先：A -> B -> C -> D -> E ->
//        System.out.print("\n广度优先：");
//        graph.bfs();

        int n = 8;
        String vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
        Graph graph = new Graph(n);
        for (String vertex : vertexs) {
            graph.insertVertex(vertex);
        }
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);

        graph.showGraph();

        System.out.print("深度优先：");
        graph.dfs();    //深度优先：1 -> 2 -> 4 -> 8 -> 5 -> 3 -> 6 -> 7 ->
        System.out.print("\n广度优先：");
        graph.bfs();    //广度优先：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 ->
    }

}

class Graph{
    private ArrayList<String> vertexList;   // 存放顶点集合
    private int[][] edges;  // 存放图对应的邻接矩阵
    private int numOfEdges; // 表示边的数目
    private boolean visited[];  // 记录某个结点是否被访问过

    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        visited = new boolean[n];
        numOfEdges = 0; // 初始化为0
    }

    /**
     * 插入一个结点
     * @param vertex  顶点
     */
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边
     * @param v1 顶点1
     * @param v2 顶点2
     * @param weight 权重
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges ++;
    }

    // 返回边的个数
    public int getNumOfEdges() {
        return numOfEdges;
    }

    // 返回结点个数
    public int getNumOfVertex() {
        return vertexList.size();
    }

    // 返回结点i的数据
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    // 返回v1和v2的权值
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    // 打印邻接矩阵
    public void showGraph() {
        System.out.println("  " + vertexList);
        int count = 0;
        for (int[] link: edges
             ) {
            System.out.println(vertexList.get(count ++ ) + " " + Arrays.toString(link));
        }
    }

    /**
    * 得到一行中的第一个邻接节点的下标
     * @param index 顶点下标
     * @return int 存在返回下标，否则返回-1
    */
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            // 存在下一个邻接节点
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
    * 根据前一个邻接节点的下标来获取下一个邻接节点
     * @param v1 顶点下标
     * @param v2 下一个邻接节点下标 A [0, 1, 1, 0, 0] 中的下标
     * @return int
    */
    public int getNextNeighbor(int v1, int v2) {
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    // 深度优先遍历
    private void dfs(int i) {
        System.out.print(getValueByIndex(i) + " -> ");
        visited[i] = true;

        int w = getFirstNeighbor(i);    // 获取一行中的第一个邻接节点
        while (w != -1) {
            if (!visited[w]) {
                dfs(w);
            }
            w = getNextNeighbor(i, w);  // 获取一行中的下一个邻接节点
        }
    }

    // 控制获取一行的邻接节点
    public void dfs() {
        // 遍历所有结点，进行dfs
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        this.visited = new boolean[getNumOfVertex()];   // 重置
    }

    // 广度优先遍历
    private void bfs(int i ) {
        int u;  // 表示队列头结点对应的下标
        int w;  // 邻接节点的下标
        //队列，记录节点访问顺序
        LinkedList linkedList = new LinkedList();
        System.out.print(getValueByIndex(i) + " -> ");
        visited[i] = true;  // 标记为已访问
        linkedList.addLast(i);
        while (!linkedList.isEmpty()) {
            u = (int) linkedList.removeFirst();
            w = getFirstNeighbor(u);    // 获取一行中的第一个邻接节点
            while (w != -1) {
                if (!visited[w]) {
                    System.out.print(getValueByIndex(w) + " -> ");
                    visited[w] = true;
                    linkedList.addLast(w);  // 入队
                }
                w = getNextNeighbor(u, w);  // 获取一行中的下一个邻接节点
            }
        }
    }

    public void bfs() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!visited[i]) {
                bfs(i);
            }
        }
        this.visited = new boolean[getNumOfVertex()];   // 重置
    }

}